House Robber

LeetCode 198 | Difficulty: Medium

Medium

Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return *the maximum amount of money you can rob tonight without alerting the police*.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

- `1 <= nums.length <= 100`

- `0 <= nums[i] <= 400`

Topics: Array, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 88 ms)

Metric	Value
Runtime	88 ms
Memory	21.7 MB
Date	2019-03-20

Solution

public class Solution {
    public int Rob(int[] nums) {
     if(nums.Length == 0) return 0;
    int[] memo = new int[nums.Length+1];
    memo[0] = 0;
    memo[1] = nums[0];
    for (int i = 1; i < nums.Length; i++)
    {
        int val = nums[i];
        memo[i+1] = Math.Max(memo[i], memo[i-1] + val);
    }
    return memo[nums.Length];
}
}

📜 2 more C# submission(s)

Submission (2022-01-19) — 123 ms, 35.7 MB

public class Solution {
    public int Rob(int[] nums) {
      int n = nums.Length;
        int prev=0, cur = nums[0];
        for(int i=1;i<n;i++)
        {
            int temp = Math.Max(nums[i]+prev, cur);
            prev = cur;
            cur = temp;
        }
        return cur;
    }
}

Submission (2022-01-19) — 168 ms, 35.6 MB

public class Solution {
    public int Rob(int[] nums) {
      int n = nums.Length;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i=1;i<n;i++)
        {
            dp[i+1] = Math.Max(nums[i]+dp[i-1], dp[i]);
        }
        return dp[n];
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.